package com.example.demo.linear;

/**
 * @author: Bin.L
 * @date: 2021/11/26 11:27
 * @Description: 稀疏数组 {https://zq99299.github.io/dsalg-tutorial/dsalg-java-hsp/03/01.html#%E5%AE%9E%E9%99%85%E9%9C%80%E6%B1%82}
 * {
 * 定义：当一个数组中 大部分元素为 0（或是同一个值） 时，可以使用 稀疏数组 来保存该数组
 * （例：使用 稀疏数组 保留类似前面的 二维数组（如棋盘、地图等等的场景），把 稀疏数组存盘，并且可以从新 恢复原来的二维数组）
 * 1、记录数组一共有 几行几列，有多少个不同的值
 * 2、把具有 不同值的元素 的 行列及值 记录在一个 小规模的数组 中，从而缩小程序的规模
 * }
 */
public class SparseArray {

    public static void main(String[] args) {
        int[][] initArray = {{0, 0, 5, 0, 0, 0}, {0, 0, 3, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 2, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}};
        // 原始数组
        printChessArray(initArray);
        System.out.println("---Two-dimensional Transform SparseArray---");
        // 转稀疏数组
        int[][] sparseArray = toSparseArray(initArray);
        printChessArray(sparseArray);
        // 还原原始数组
        System.out.println("----SparseArray Transform Two-dimensional Array----");
        printChessArray(toTwoDimensional(sparseArray));
    }

    /**
     * Two-dimensional Transform SparseArray
     *
     * @param chessArr
     */
    public static int[][] toSparseArray(int[][] chessArr) {
        // 1.遍历数组有效数据个数
        int sum = 0;
        for (int[] row : chessArr) {
            for (int data : row) {
                if (data != 0) {
                    ++sum;
                }
            }
        }
        // 2.创建稀疏数据
        int[][] sparseArray = new int[sum + 1][3];
        int count = 0;
        for (int row = 0; row < chessArr.length; row++) {
            for (int clo = 0; clo < chessArr[row].length; clo++) {
                // 记录汇总数据
                if (row == 0 && clo == 0) {
                    sparseArray[count][0] = chessArr.length;
                    sparseArray[count][1] = chessArr[row].length;
                    sparseArray[count][2] = sum;
                    count++;
                }
                // 记录不为0的数据
                if (chessArr[row][clo] != 0) {
                    sparseArray[count][0] = row;
                    sparseArray[count][1] = clo;
                    sparseArray[count][2] = chessArr[row][clo];
                    count++;
                }

            }
        }
        return sparseArray;
    }

    /**
     * SparseArray Transform Two-dimensional Array
     *
     * @param sparseArray
     */
    public static int[][] toTwoDimensional(int[][] sparseArray) {
        // 1.还原数组大小
        int[][] chessArr = new int[sparseArray[0][0]][sparseArray[0][1]];

        // 2.还原数组值
        for (int i = 1; i < sparseArray.length; i++) {
            chessArr[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return chessArr;
    }


    /**
     * print Two-dimensional
     *
     * @param chessArr
     */
    public static void printChessArray(int[][] chessArr) {
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.printf("%-2d\t", data);
            }
            System.out.println("");
        }
    }

}
